/**
 * 376.摆动序列
 */
public class Exerciser2 {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n]; // 以i位置结尾的状态为正数
        int[] g = new int[n]; // 以i位置结尾的状态为负数
        for(int i = 0;i < n;i++) {
            f[i] = g[i] = 1;
        }

        int ret = 1;
        for(int i = 1;i < n;i++) {
            for(int j = 0;j < i;j++) {
                if(nums[i] > nums[j]) {
                    // 为正数，所以j这个位置的状态为负数
                    f[i] = Math.max(g[j] + 1,f[i]);
                }else if(nums[i] < nums[j]) {
                    // 为负数，所以j这个位置的状态为正数
                    g[i] = Math.max(f[j] + 1,g[i]);
                }
            }
            ret = Math.max(ret,Math.max(f[i],g[i]));
        }

        return ret;
    }
}
